#include <stdio.h>
#include <stdlib.h>
#include <map>
#include <vector>

using namespace std;

int nsieve(int m){
   //map< int, bool > prime;
   //vector< bool > prime(m);
   bool *prime = new bool[m];
   for(int i = 2; i < m; ++i){
      prime[i] = true;
   }
   int count = 0;
   for(int i = 2; i < m; ++i){
      if(prime[i]){
         for(int j = i+i; j < m; j += i){
            prime[j] = false;
         }
         count += 1;
      }
   }
   return count;
}

int main(){
   int m = 5120000;
   printf("%i primes in %i\n", nsieve(m), m);
   return 0;
}

